package com.fe.class04;

import java.util.Arrays;

/**
 * @Description 迭代方式实现归并排序
 * @Author sosuke :-)
 * @Date 2021/12/14 06:23
 */
public class Code02_MergeSort_Iteration {

    /**
     * O(N * logN)
     * 步长一共变化了logN次，步长变化一次，需要迭代操作O(N)
     *
     * @param arr
     */
    public static void mergeSort(int[] arr) {
        if (arr == null || arr.length < 2) return;
        int N = arr.length;
        int mergeSize = 1; // 步长（一组的长度）
        // mergeSize 倍增
        while (mergeSize < N) {
            int L = 0; // 当前左组的第一位
            // 左组第一位右移
            while (L < N) { // 左组的第一位如果>=N，则结束
                // int M = L + mergeSize - 1; // 当前左组的最后一位
                // if (M >= N) { // 左组不够则此次不合并
                //     break;
                // }
                if (mergeSize >= N - L) { // 说明左组不够，此次不合并
                    break;
                }
                int M = L + mergeSize - 1;
                int R = Math.min(M + mergeSize, N - 1); // 右组可能不够
                merger(arr, L, M, R); // 左组右组合并
                L = R + 1; // 移动到下一个左组首位
            }
            // mergeSize 大于N/2，则 mergeSize << 1 一定大于N，不需要继续执行，防止溢出
            if (mergeSize > N / 2) {
                break;
            }
            mergeSize <<= 1; // 步长乘2
        }
    }

    /**
     * 合并操作
     * 左组arr[L...M]一定有序  右组arr[M+1...R]一定有序
     *
     * @param arr
     * @param L
     * @param M
     * @param R
     */
    private static void merger(int[] arr, int L, int M, int R) {
        int[] help = new int[R - L + 1];
        int i = 0;
        int p1 = L;
        int p2 = M + 1;
        // 都没有越界的情况下，谁小拷贝谁，相等则先拷贝左组
        while (p1 <= M && p2 <= R) {
            help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }
        // p2越界，拷贝p1剩余的数
        while (p1 <= M) {
            help[i++] = arr[p1++];
        }
        // p1越界，拷贝p2剩余的数
        while (p2 <= R) {
            help[i++] = arr[p2++];
        }
        System.arraycopy(help, 0, arr, L, help.length);
    }

    public static void main(String[] args) {
        int testTime = 100000; // 测试次数
        int maxSize = 10; // 数组数据个数
        int maxValue = 200; // 数组中最大值
        for (int i = 0; i < testTime; i++) {
            int[] arr1 = generateRandomArray(maxSize, maxValue);
            int[] arr2 = Arrays.copyOf(arr1, arr1.length);
            mergeSort(arr1);
            Arrays.sort(arr2);
            if (!Arrays.equals(arr1, arr2)) {
                System.out.println("Fuck");
                System.out.println(Arrays.toString(arr1));
                System.out.println(Arrays.toString(arr2));
                return;
            }
        }
        System.out.println("Nice");
        int[] arr = generateRandomArray(maxSize, maxValue);
        System.out.println(Arrays.toString(arr));
        mergeSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) ((maxValue + 1) * Math.random());
        }
        return arr;
    }
}
